Lamping, J. and Rao, R., “The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies”, Journal of Visual Languages and Computing, Vol. 7, 1996, pp. 33-55, disclose techniques for laying out a hierarchy on a hyperbolic plane such that distance between parent and child and between siblings is approximately the same everywhere. A recursive algorithm lays out each node based on local information, allocating a wedge of the hyperbolic plane for the node's descendants. The algorithm places all the children along an arc in the wedge, at an equal distance from the parent node, and at least a minimum distance apart from each other. The layout of a node depends only on the layout of its parent and on the node structure of two or three generations starting from the parent. Therefore, the layout can be done incrementally, such as by initially laying out the nodes nearest the root and by then adding more nodes as more of the structure is traversed. Lamping et al., U.S. Pat. No. 5,590,250, disclose similar layout techniques in which each node has a data structure that includes its position and radius and, if it has children, a link to a list of children; complex numbers are used to represent positions in the hyperbolic plane.
Munzner, T., and Burchard, P., “Visualizing the Structure of the World Wide Web in 3D Hyperbolic Space”, in Proceedings of the VRML '95 Symposium (San Diego, Calif., Dec. 13-16, 1995), ACM SIGGRAPH, 1995, pages 33-38, disclose techniques for layout of a graph in the hyperbolic plane that can be used with directed graphs with cycles. The hyperbolic length of an edge connecting two nodes is obtained using hyperbolic functions and the angles between edges incident on the two nodes. Directed graphs with cycles can be embedded in hyperbolic manifolds-spaces which can wrap around and close up on themselves, or in standard hyperbolic space by filling in backlink edges.
Matsuura, T., Taniguchi, K., Masuda, S., and Nakamura, T., “A Graph Editor for Large Trees with Browsing and Zooming Capabilities”, Systems and Computers in Japan, Vol. 24, No. 8, 1993, pp. 35-46, disclose a library program which allows direct manipulation of a large tree on a display. When a node or subtree is added or deleted, the data structure is updated; the layout for each node is calculated based on the graph layout algorithm, and each node and edge is redrawn. The layout algorithm determines, for each non-root node, a relative position value that is the difference between the node's x-coordinate and its parent's x-coordinate. The y-coordinate, on the other hand is determined by the level of the node, and therefore is determined when the coordinates of the root node are specified. When a part of the tree is deleted or a subtree is added, ancestors are traced to update the layout.
The invention addresses problems in laying out node-link structures in a space with negative curvature, such as hyperbolic space.
With the techniques described by Lamping and Rao and with other conventional techniques for negative curvature layout, if a structure changes after it is displayed, a new layout must typically be done for at least a large part of the structure as changed and then it must be redisplayed. Performing layout on a large structure is slow, and, when taken together with redisplay, may prevent a user from effectively interacting with the changed structure. Although these problems are especially acute for changing structures, they also arise when operations are performed that require frequent layout of a static structure or of parts of a static structure.
The layout techniques for static structures described by Lamping and Rao have certain characteristics that mandate layout of at least a large part of the structure. The layout techniques for static structures make decisions at each node that depend on layout decisions higher in the tree and at its sibling nodes; as a result, adding or deleting a child of a node mandates that the layout be redone for all descendants of the node and of any of its siblings. Also, the layout techniques for static structures save only the node's position in the hyperbolic plane; any change in the structure that would change a node's position requires repeating the layout of its siblings and all of its descendants.
The invention alleviates problems resulting from layout of large structures by providing techniques that make it possible to perform local layout of a node-link structure in a space with negative curvature such as hyperbolic space or the hyperbolic plane. The techniques obtain nearby relationship data for an element, indicating information about nearby node-link relationships. Then the techniques use the nearby relationship data to obtain layout data indicating the element's position relative to a parent in the space with negative curvature.
If the element and the parent are nodes, for example, the layout data can include position displacement data indicating a distance between the parent's position and the element's position and angle displacement data indicating an angular difference between an incoming link to the parent and the outgoing link from the parent to the element. In an especially elegant implementation, the layout data include only the position displacement data and the angle displacement data.
The nearby relationship data can be obtained by obtaining, for each of a set of children of the parent, a count of grandchildren of the parent. The set of children of the parent includes the element and can also include other children that are being or have been laid out in the negatively curved space. The counts of grandchildren can be used to obtain a radius and an angle for each of the set of children. The radii and angles can then be used to obtain a position displacement and an angle displacement between the parent and the element. The angle displacement can be compared with a previous angle displacement to determine whether to lay out children of the element.
The nearby node-link relationships can include only relationships among the parent and the parent's children and grandchildren.
The new techniques can be implemented iteratively, with each iteration identifying elements to be laid out and, for each identified element, obtaining nearby relationship data and layout data. For example, if a series of iterations is performed in response to an insertion or deletion event, the identified elements can include elements affected by the insertion or deletion. The identified elements for each iteration can also include elements added to the structure during a preceding iteration. Before the series, a weight can be obtained for each iteration, for use in obtaining layout data during the iteration.
The new techniques are advantageous in laying out a dynamic node-link structure because when an element is deleted or inserted only a few nearby elements need to be laid out again. The techniques also obtain an element's position relative to a parent rather than an absolute position, making it possible to change the position of an element and all its descendants by making a single change or a small constant number of localized changes in the data structure.
The new techniques are also advantageous because they can be used in a variety of situations in which it is desirable to lay out part of a node-link structure. Thus, the new techniques are not only applicable to a dynamic node-link structure, but also to a static structure that can only be laid out and displayed in fragments because not all of the structure is available in memory. The techniques are especially advantageous for laying out a tree that is a partial representation of a directed graph in which nodes have multiple in-links—a shared branch of such a tree need only be completely laid out once for all of its occurrences, since only the relative position of the uppermost elements will differ between occurrences.
The techniques are also advantageous for animation of a change involving only part of a structure. For example, if insertions or deletions are made in a structure, it may be desirable to animate the transition in a way that only changes positions of elements that are near the insertion or deletion. The techniques make it possible to rapidly perform a series of layouts, one for each animation step, in which only the positions of elements near insertions or deletions are changed. As a result, animation performance improves and a simpler animation algorithm can be used. The algorithm can continuously change only a small number of variables, such as an angle and radius for each node that is near an insertion or a deletion.
Another advantage is that the new techniques provide layouts from which a display can be generated starting at any arbitrary element, rather than always starting at the root node or at the bottom leaves of a structure as in conventional techniques.
Yet another advantage is that an element's position relative to its parent can always be expressed with adequate precision. In contrast, if an element's absolute position in a hyperbolic plane is used, a large structure could exhaust the available floating point numbers.
The following description, the drawings, and the claims further set forth these and other aspects, objects, features, and advantages of the invention.